class Solution {
public:
    string decodeString(string s)
    {
        stack<string> st1;
        stack<int> st2;
        st1.push("");
        for (int i = 0; i < s.size(); )
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (i < s.size() && s[i] >= '0' && s[i] <= '9')
                {
                    tmp = tmp * 10 + s[i] - '0';
                    i++;
                }
                st2.push(tmp);
            }
            else if (s[i] == '[')
            {
                i++;
                string tmp;
                while (i < s.size() && s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                st1.push(tmp);
            }
            else if (s[i] == ']')
            {
                i++;
                string tmp;
                int count = st2.top(); st2.pop();
                string str = st1.top(); st1.pop();
                while (count--) tmp += str;
                st1.top() += tmp;
            }
            else
            {
                while (i < s.size() && s[i] >= 'a' && s[i] <= 'z')
                {
                    st1.top() += s[i];
                    i++;
                }
            }
        }
        return st1.top();
    }
};
class MinStack
{
    stack<int> st1;
    stack<int> st2;
public:
    MinStack()
    {

    }

    void push(int val)
    {
        if (st1.empty())
        {
            st1.push(val);
            st2.push(val);
        }
        else
        {
            if (val <= st2.top()) st2.push(val);
            st1.push(val);
        }
    }

    void pop()
    {
        if (st1.top() == st2.top())
        {
            st1.pop();
            st2.pop();
        }
        else st1.pop();
    }

    int top()
    {
        return st1.top();
    }

    int getMin() {
        return st2.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */
class Solution {
public:
    bool isValid(string s)
    {
        stack<char> st;
        for (auto ch : s)
        {
            if (ch == '(' || ch == '[' || ch == '{') st.push(ch);
            else
            {
                if (st.size() == 0) return false;
                if ((ch == ')' && st.top() != '(') || (ch == ']' && st.top() != '[') || (ch == '}' && st.top() != '{'))
                {
                    return false;
                }
                st.pop();
            }
        }
        if (st.size()) return false;
        return true;
    }
};
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        int m = nums1.size(), n = nums2.size();
        if (m > n) return findMedianSortedArrays(nums2, nums1);
        int LeftCount = (m + n + 1) / 2;
        int left = 0, right = m;
        while (left < right)
        {
            int i = left + (right - left + 1) / 2;
            int j = LeftCount - i;
            if (nums1[i - 1] > nums2[j]) right = i - 1;
            else left = i;
        }
        int i = left;
        int j = LeftCount - i;
        int nums1LeftMin = i == 0 ? INT_MIN : nums1[i - 1];
        int nums1RightMax = i == m ? INT_MAX : nums1[i];
        int nums2LeftMin = j == 0 ? INT_MIN : nums2[j - 1];
        int nums2RightMax = j == n ? INT_MAX : nums2[j];

        if ((m + n) % 2 == 1) return max(nums1LeftMin, nums2LeftMin);
        else return (max(nums1LeftMin, nums2LeftMin) + min(nums1RightMax, nums2RightMax)) / 2.0;

    }
};